//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 
//
// 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 
//
// 
//
// 
//
// 示例 1: 
//
// 
//输入: numRows = 5
//输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
// 
//
// 示例 2: 
//
// 
//输入: numRows = 1
//输出: [[1]]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= numRows <= 30 
// 
// Related Topics 数组 动态规划 👍 563 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>>result = new ArrayList<>();

        int[][] dp = new int[numRows][numRows];
        for(int i = 0; i < numRows; i++){
            List<Integer>row = new ArrayList<>();
            for (int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    dp[i][j] = 1;
                }else {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
                row.add(dp[i][j]);
            }
        result.add(row);
    }
        return result;
}
//leetcode submit region end(Prohibit modification and deletion)
